#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "unordered_map"

using namespace std;
/*HJJ QQ479287006
 *给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点
 输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
示例 2：
输入：root = [1]
输出：["1"]
 * */

vector<string> ret;
vector<int> temp;

void binaryTreePathsBack(TreeNode *root) {

    if (root == nullptr)
        return;
    temp.push_back(root->val);
    if (!root->left && !root->right) {
        string s = "";
        for (const auto &item : temp) {
            s = s + to_string(item) + "->";
        }
        s.pop_back();
        s.pop_back();
        ret.push_back(s);

        return;// TODO 这里加ret为什么会出错后续是（没有if后续是 binaryTreePathsBack(root->left); binaryTreePathsBack(root->right)） 如果 直接ret 那边没有pop_back();
        //这个对比一下offer12 那个有返回值那样写没毛病 难道这种得写成if if的吗 https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof
        //反正是 一般不加ret 都不会出错 啊但是加了有可能出错
    }
    if (root->left) {
        binaryTreePathsBack(root->left);
        temp.pop_back();
    }

    if (root->right) {
        binaryTreePathsBack(root->right);
        temp.pop_back();
    }


}
/*
 *
 * 这个回溯就要很⼤的问题，我们知道，回溯和递归是⼀⼀对应的，有⼀个递归，就要有⼀个回溯，这么写的话相当
于把递归和回溯拆开了， ⼀个在花括号⾥，⼀个在花括号外。
所以回溯要和递归永远在⼀起，世界上最遥远的距离是你在花括号⾥，⽽我在花括号外！
 * **/
vector<string> binaryTreePaths(TreeNode *root) {
    binaryTreePathsBack(root);
    return ret;
}

//非递归的方式 TODO 我似乎不会啊
//vector<string> binaryTreePaths(TreeNode* root) {
//    stack<TreeNode*> treeSt;// 保存树的遍历节点
//    stack<string> pathSt;   // 保存遍历路径的节点
//    vector<string> result;  // 保存最终路径集合
//    if (root == NULL) return result;
//    treeSt.push(root);
//    pathSt.push(to_string(root->val));
//    while (!treeSt.empty()) {
//        TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中
//        string path = pathSt.top();pathSt.pop();    // 取出该节点对应的路径
//        if (node->left == NULL && node->right == NULL) { // 遇到叶子节点
//            result.push_back(path);
//        }
//        if (node->right) { // 右
//            treeSt.push(node->right);
//            pathSt.push(path + "->" + to_string(node->right->val));
//        }
//        if (node->left) { // 左
//            treeSt.push(node->left);
//            pathSt.push(path + "->" + to_string(node->left->val));
//        }
//    }
//    return result;
//}